#include "warshalfloyd.h"
#include "genlib.h"
#include "helpers.h"

int minimum(int i, int j);

void warshall(int **graph, int graphSize){
	int i, j, k;

	for(k = 0; k < graphSize; k++){
		for(i = 0; i < graphSize; i++){
			for(j = 0; j < graphSize; j++){
				graph[i][j] = graph[i][j] || graph[i][k] && graph[k][j];
			}
		}
	}
	printf("\nWarshall matrix\n");
	printGraph(graph,graphSize);
	k = 0;
	for(j = 0; j < graphSize; j++){
		for(i = 0; i < graphSize; i++){
			if(graph[i][j] != 0){
				k++;
			}
		}
	}
	printf("Paths in transitive closure: %d\n\n",k);
}

void floyd(int **graph, int graphSize){
	int i, j, k;

	for(k = 0; k < graphSize; k++){
		for(i = 0; i < graphSize; i++){
			for(j = 0; j < graphSize; j++){
				graph[i][j] = minimum(graph[i][j], graph[i][k]+graph[k][j]);
			}
		}
	}
	printf("\nFloyd matrix\n");
	printGraph(graph,graphSize);
	k = 0;
	for(j = 0; j < graphSize; j++){
		for(i = 0; i < graphSize; i++){
			if(graph[i][j] != 0 && graph[i][j] != 999){
				k++;
			}
		}
	}
	printf("Conencted pairs: %d\n\n",k);
}

int minimum(int i, int j){
	if(i > j)
		return j;
	else
		return i;
}